#ifndef _DLIST_H_
#define _DLIST_H_

#include"utili.h"
 

#define DListElem_Type int



typedef struct DListNode {
	DListElem_Type data;
	struct DListNode* next;
	struct DListNode* prev;
}DListNode;

typedef DListNode* DList;

void DListInit(DList* phead);
void DListPushBack(DList* phead, DListElem_Type v);
void DListPushFront(DList* phead, DListElem_Type v);
void DListDeleteVal(DList* phead, DListElem_Type v);
void DListInsertVal(DList* phead, DListElem_Type v);
void DListReverse(DList* phead);

void DListInit(DList* phead) {
	*phead = NULL;
}
void DListPushBack(DList* phead, DListElem_Type v) {
	DListNode* s = (DListNode*)malloc(sizeof(DListNode));
	assert(s != NULL);
	s->data = v;
	s->prev = s->next = NULL;
	if (*phead == NULL) {
		*phead = s;
	}
	else {
		while (p->next != NULL) {
			p = p->next;
		}
		s->prev = p;
		p->next = s;
	}
}
void DListPushFront(DList* phead, DListElem_Type v) {
	DListNode* s = (DListNode*)malloc(sizeof(DListNode));
	assert(s != NULL);
	s->data = v;
	s->prev = s->next = NULL;
	if (*phead != NULL){
		(*phead)->prev = s;
		s->next = *phead;
	}
	*phead = s;
}
void DListDeleteVal(DList* phead, DListElem_Type v)
{
	assert(*phead != NULL);
	
	DListNode* p = *phead;
	while (p!= NULL &&p->data != v) {
		
		p = p->next;
		}
	if (p == NULL) {
		return;
	}
	if (p->prev != NULL) {
		p->prev->next = p->next->next;
	}
	if (p->next != NULL) {
			p->next->prev = p->prev;
	}

	free(p);
}
void DListInsertVal(DList* phead, DListElem_Type v) {
	DListNode* s = (DListNode*)malloc(sizeof(DListNode));
	assert(s != NULL);
	s->data = v;
	s->prev = s->next = NULL;
	if (*phead == NULL) {
		*phead = s;
		return;
	}
	DListNode* p = *phead;
while (p!= NULL&&p->data<v) {
	p = p->next;
}
if (p->prev == NULL) {
	s->next = *phead;
	(*phead)->prev = s;
	*phead = s;
	return;
}
if (p == NULL) {
	s->next = NULL;
	s->prev = p->prev;
	return;
}
else {
	s->next = p;
	s->prev = p->prev;
	/*p->prev->next = s;
	p->prev = s;
	*/
	s->next->prev = s;
	s->prev->next = s;
}
void DListReverse(DList * phead) {
	if(*phead==NULL&&(*phead)->next=NULL){
		return;
	}
	DListNode* p = *phead->next;
	while (p != NULL) {
		DListNode* q = p->next;
		p->next = *phead;
		(* phead)->prev = p;
		*phead = p;
		p = q;
	}

#endif // !_DLIST_H_

